package com.zyk.leetcode;

import java.util.HashMap;

/**
 * @author zhangsan
 * @date 2021/5/10 15:19
 */
public class C337 {

    // 二叉树上, 打家劫舍
    public static int rob(TreeNode root) {
        return process(root);
    }


    public static int process(TreeNode cur) {
        if(cur == null)
            return 0;
        int p1 = process(cur.left) + process(cur.right);    // 不要当前
        int p2 = cur.val;
        if(cur.left != null) {
            p2 += process(cur.left.left);
            p2 += process(cur.left.right);
        }
        if(cur.right != null) {
            p2 += process(cur.right.left);
            p2 += process(cur.right.right);
        }
        return Math.max(p1, p2);
    }

    // 二叉树上, 打家劫舍
    public static int rob2(TreeNode root) {
        HashMap<TreeNode, Integer> dp = new HashMap<>();
        return process2(root, dp);
    }


    public static int process2(TreeNode cur, HashMap<TreeNode, Integer> dp) {
        if(cur == null)
            return 0;
        if(dp.containsKey(cur)) return dp.get(cur);
        int p1 = process2(cur.left, dp) + process2(cur.right, dp);    // 不要当前
        int p2 = cur.val;
        if(cur.left != null) {
            p2 += process2(cur.left.left, dp);
            p2 += process2(cur.left.right, dp);
        }
        if(cur.right != null) {
            p2 += process2(cur.right.left, dp);
            p2 += process2(cur.right.right, dp);
        }
        int ans = Math.max(p1, p2);
        dp.put(cur, ans);
        return ans;
    }


    // for test
    public static void main(String[] args) {

    }

}
